#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
using namespace std;

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
       set<vector<int> > rtn;
       vector<vector<int> > rtn2;
    
       //sort the input data
       sort(num.begin(), num.end());
       for (int i = 0; i < num.size(); i++) {
           int need = 0 - num[i];
           for (int j = i + 1, k = num.size()-1; j < k; ) {
               vector<int> ans;
               if (num[j] + num[k] == need) {
                   ans.push_back(num[i]);
                   ans.push_back(num[j]);
                   ans.push_back(num[k]);
                   if (rtn.count(ans) == 0) {
                       rtn.insert(ans);
                       rtn2.push_back(ans);
                   }
                   j++;
                   k--;
               } else if (num[j] + num[k] > need) {
                   k--;
               } else {
                   j++;
               }
           }
       }
       return rtn2;
    }
};
        
int main(int argc, char **argv)
{
    Solution mySolution;
    int input[] = {-2,0,1,1,2};
    vector<int> test;
    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        test.push_back(input[i]);
    }
    vector<vector<int> > result = mySolution.threeSum(test);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}
